package com.leet.backtracking;

import java.util.ArrayList;
import java.util.List;

public class Exist {
    boolean flag = false;
    // 精髓在于borad
    public void backtracking(char[][] board, String word,boolean[][] vis,int i,int j,int k){
        if(i<0||j<0||i>=board.length||j>=board[0].length||vis[i][j]||
                board[i][j]!=word.charAt(k)||k > word.length()-1){
            return;
        }
        if(k == word.length()-1){
            flag = true;
            return;
        }
        vis[i][j] = true;
        backtracking(board,word,vis,i+1,j,k+1);
        backtracking(board,word,vis,i,j+1,k+1);
        backtracking(board,word,vis,i-1,j,k+1);
        backtracking(board,word,vis,i,j-1,k+1);
        vis[i][j] = false;
    }
    public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<>();
        StringBuilder s = new StringBuilder();

        boolean[][] vis = new boolean[board.length][board[0].length];

        for(int i = 0;i < board.length;i++){
            for (int j = 0; j < board[0].length; j++) {

                for(String word:words){
                    backtracking(board,word,vis,i,j,0);
                    if(flag&&!ans.contains(word)) {
                        ans.add(word);
                    }
                    // 对于每一个单词都得重新flag置为false
                    flag = false;
                }
            }


        }
        return ans;}}